package com.lisp.algorithm.test.sort;

import java.util.Arrays;

public class MergeSort {

	public static void main(String[] args) {
		int data[] = {109, 9, 19, 28, 43, 2, 7, 9, 190, 9, 9, 28, 
				43, 2, 7, 9, 190, 9, 9};
		mergeSort(data, 0, data.length-1);
		System.out.println(Arrays.toString(data));
	}
	
	// p inclusive, r inclusive, p <= q <= r
	private static void merge(int data[], int p, int q, int r) {
		int headPart[] = new int[q-p+1];
		System.arraycopy(data, p, headPart, 0, q-p+1);
		
		int i=0, j=q+1, ordered = p;
		while(i<=q-p && j<=r && ordered<=r) {
			if(headPart[i] < data[j]) {
				data[ordered++] = headPart[i];
				i++;
			} else {
				data[ordered++] = data[j];
				j++;
			}
		}
		if(i <= q-p) {
			System.arraycopy(headPart, i, data, ordered, q-p-i+1);
		}
	}
	
	// start inclusive, end inclusive
	private static void mergeSort(int data[], int start, int end) {
		if(end > start) {
			int p = start;
			int q = (end + start)/2;
			int r = end;
			mergeSort(data, p, q);
			mergeSort(data, q+1, r);
			merge(data, p, q, r);
		}
	}
}
